
/*
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n;
int f[N][N];
int main()
{
	cin>>n;
	for(int i=1 ;i <= n; i++)
	  for(int j=1 ;j <=i; j++)
	     cin>>f[i][j];
    for(int i=n-1 ;i >= 1 ;i--)
       for(int j=1 ;j <= i;j++)
		  f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
	cout<<f[1][1]<<endl;
	return 0;
}
*/
/*
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n;
int f[N][N], a[N][N];
int main()
{
	cin>>n;
	for(int i=1 ;i <= n;i++)
	   for(int j=1;j <= i;j++)
	      cin>>a[i][j];
	for(int i=1; i<=n; i++)
       f[n][i]=a[n][i];
    for(int i=n-1; i>=1; i--)
       for(int j=1; j<=n ;j++)
       {
	   	   f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
	   }
	   cout<<f[1][1]<<endl;
	return 0;
}
*/
/*
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int q[N], a[N];
int main()
{
	cin>>n;
	for (int i=0;i <=n;i++)
	   cin>>q[i];
	for (int i=0;i <=n;i++)
	{   
	   a[i]=1;
	   for (int j=0; j<i;j++)
	     if (q[j]<q[i])
	     q[i] = max(q[i],q[j]+1);
	}  
	int res=0;
	for (int i=0; i<n; i++)
	   res=max(q[i],res);
	cout<<res<<endl;
	return 0;
}
*/




































